Date: Wed, 20 Nov 1996 23:18:35 GMT
Server: NCSA/1.5
Content-type: text/html

<!DOCTYPE HTML PUBLIC "-//W3O//DTD W3 HTML 2.0//EN">
<HEAD>
<TITLE>22C:21 Home Page</TITLE>
</HEAD>
<BODY>
<P>
<H2>
<b> 22C:21 Algorithms and Data Structures --- Spring 1996</b></H2>
<P>
<H5>
MWF 1:30, Jessup Hall 221</H5>
<P>
<b> PROFESSOR:</b> <!WA0><a href="http://www.cs.uiowa.edu/~cremer">Jim Cremer</a>, 201N MacLean, E-mail: cremer@cs.uiowa.edu, Office hours: 2:30-3:30 T, 10:30-11:30 F, or by appointment<BR> 
<P>
<b> TA:</b> Jun Tu, 255D McBride, jun@cs.uiowa.edu, Office Hours: 3:30-4:30 W, 1:30-2:30 Th<BR>
<P>
<HR>
<H2> WHAT'S NEW (Last updated Monday, 5/13/96) </H2>

<UL>
<LI> Complete scores for the semester and the mapping from scores to
course letter grades are available in the <!WA1><A HREF=#grades>Grades
section</A>. To see or pick up your graded final, please stop by my
office.
</UL>

<HR>
<UL>
<LI> <!WA2><A HREF=#homework>Homework assignments</A>
<LI> <!WA3><A HREF=#grades>Scores and grades</A>
<LI> <!WA4><A HREF=#schedule>Goals, content, and schedule</A>
<LI> <!WA5><A HREF=#books>Textbook and Supplemental books</A>
<LI> <!WA6><A HREF=#grading>Requirements and grading</A>
<LI> <!WA7><A HREF=#lateness>Late assignment policy</A>
<LI> <!WA8><A HREF=#collaboration>Policy on Collaboration</A>
<LI> <!WA9><A HREF=#prereq>Prerequisites</A>
<LI> <!WA10><A HREF=#langnote>Note on Language for Programming Assignements</A>
<LI> <!WA11><A HREF=#solns> Homework solutions, useful code, sample exams, etc.</A>
</UL>

<HR>
<H2>
<A NAME = prereq> Prerequisites </H2>
22C:17, 22C:18, and 22C:19 (or permission of instructor)

<HR>
<H2>
<A NAME=schedule> Course goals, content, and schedule
</H2>

<P>
The aim of the course is to gain experience with the major paradigms and data 
structures used in creating algorithms, and with basic methods for analyzing 
the time and space requirements of programs. We will cover most of the textbook.
The tentative schedule is:
<P>
<PRE>
  Week 1              Intro and Ch 1 (math background, induction, recursion)
  Week 2              Ch 2 (algorithm analysis notation and techniques), a bit of 7.6 and 10.2
  Week 3              quick review of Ch3, Ch 4 (trees)
  Week 4              Ch 5 (hashing)
  Weeks 4 and 5       Ch 6 (priority queues)
  Week 6              Ch 7 (sorting)
  Week 7 (February 28)     Exam 1,in class
  Weeks 7 and 8       Ch 8 (disjoint sets)
  Weeks 8 and 9       Ch 9 (graphs)
  Week 10             SPRING BREAK
  Week 11             Ch 9 (graphs), including a bit extra on decidability, tractability, complexity
  Weeks 12 and 13     Ch 10 (algorithm techniques), including greedy methods, dynamic
                          programming, more divide-and-conquer
  Week 14 (April 17)  Exam 2, in class
  Week 15             Ch 10.5 backtracking search/games (TENTATIVE)
  Week 16             Ch 11 (amortized analysis)
  May 10 (Friday)     FINAL EXAM, 9:45 a.m.          
</PRE>

<HR>

<H2>
<A NAME=books> Textbook
</H2>
<P> Weiss, <em> Data Structures and Algorithm Analysis</em>, Benjamin-Cummings, Second Edition, 1995.
<P>

<H2> Supplemental Books (on reserve in Math Library)</H2> 
<P>
 Cormen, Leiserson, and Rivest, <em> Introduction to Algorithms</em>, McGraw-Hill, 1990<BR> 
 Aho, Hopcroft, and Ullman, <em> Data Structures and Algorithms</em>, Addison-Wesley, 1983
<P>

<HR>
<H2>
<A NAME=grading> Requirements and grading
</H2>
<P>
Course grades will be based on ten (or so) homework sets, two
midterm exams, and the final exam.  There will be some small
programming assignments.  Programming problems will usually be given
as part of regular written homework assignments; there will not be a
separate grading category for programming assignments.  Class
participation and effort may be taken into account in determining grades in
borderline situations.  The components will be weighted roughly as
follows:
<PRE>
		Homeworks assignments         35%
		Midterm exams                 20% each
		Final exam                    25%
<P>
</PRE>

<HR>
<H2>
<A NAME=lateness> Late assignment policy
</H2>
<P>
All assignments are due at the beginning of class.  In other cases,
assignments turned in within 24 hours will receive a 20% penalty, and
those turned in 24 to 48 hours late will receive a 50% penalty.
(Exception --- each student may turn in one homework assignment up to
two days late with no penalty.)  Regrade requests must be made within
one week of when the assignments are returned in class.

<HR>
<H2>
<A NAME=collaboration> Policy on collaboration
</H2>
<P>
Homework and programming assignments should be done alone.  It is 
reasonable to discuss general approaches to problem solution or 
algorithm design with other students but the bulk of the work 
must be done alone.  Working out details, sharing in the write-up 
or sharing or copying code will be treated as a violation of the 
academic integrity rules.

<HR>
<H2> <A = langnote> Note on Language for Progamming Assignments </H2>
<P>
Program source code in the book is in Pascal.  However, for course 
programming assignments, you will be free to use your choice of Pascal, C, or 
C++ (or another language if approved by the instructor).

<HR>
<H2>
<A NAME=homework> Homework Assignments
</H2>
<P>
<UL>
<LI> <!WA12><A HREF=http://www.cs.uiowa.edu/~cremer/courses/cs21/homeworks/hw8/hw8.html>Homework 8</A> (HTML version).<BR>
     <!WA13><A HREF=http://www.cs.uiowa.edu/~cremer/courses/cs21/homeworks/hw8.ps>Homework 8</A> (Postscript version).
<LI> Official test data for Homework 8 (must turn in 
runs of your program on these files):<br>
<!WA14><A href=http://www.cs.uiowa.edu/~cremer/courses/cs21/homeworks/wordlist1>wordlist1</A>,
<!WA15><A href=http://www.cs.uiowa.edu/~cremer/courses/cs21/homeworks/wordlist2>wordlist2</A>,
<!WA16><A href=http://www.cs.uiowa.edu/~cremer/courses/cs21/homeworks/wordlist3>wordlist3</A>
<BR>
Some other test data for Homework 8:<BR>
<!WA17><A href=http://www.cs.uiowa.edu/~cremer/courses/cs21/homeworks/extra-wordlist1>extra-wordlist1</A>,
<!WA18><A href=http://www.cs.uiowa.edu/~cremer/courses/cs21/homeworks/extra-wordlist2>extra-wordlist2</A>,
<!WA19><A href=http://www.cs.uiowa.edu/~cremer/courses/cs21/homeworks/extra-wordlist3>extra-wordlist3</A><br>
<LI> <!WA20><A HREF=http://www.cs.uiowa.edu/~cremer/courses/cs21/homeworks/hw7/hw7.html>Homework 7</A> (HTML version).<BR>
     <!WA21><A HREF=http://www.cs.uiowa.edu/~cremer/courses/cs21/homeworks/hw7.ps>Homework 7</A> (Postscript version).
<LI> <!WA22><A HREF=http://www.cs.uiowa.edu/~cremer/courses/cs21/homeworks/hw6/hw6.html>Homework 6</A> (HTML version).<BR>
     <!WA23><A HREF=http://www.cs.uiowa.edu/~cremer/courses/cs21/homeworks/hw6.ps>Homework 6</A> (Postscript version).
<LI> Official test data for Homework 6 (must turn in 
runs of your program on these files):
<!WA24><A href=http://www.cs.uiowa.edu/~cremer/courses/cs21/homeworks/circuit1.text>circuit1</A>,
<!WA25><A href=http://www.cs.uiowa.edu/~cremer/courses/cs21/homeworks/circuit2.text>circuit2</A>,
<!WA26><A href=http://www.cs.uiowa.edu/~cremer/courses/cs21/homeworks/circuit3.text>circuit3</A>, 
<!WA27><A href=http://www.cs.uiowa.edu/~cremer/courses/cs21/homeworks/circuit4.text>circuit4</A> <BR>
<!WA28><A href=http://www.cs.uiowa.edu/~cremer/courses/cs21/homeworks/path1.text>path1</A>,
<!WA29><A href=http://www.cs.uiowa.edu/~cremer/courses/cs21/homeworks/path2.text>path2</A>,
<!WA30><A href=http://www.cs.uiowa.edu/~cremer/courses/cs21/homeworks/path3.text>path3</A>
<BR>
Some other test data for Homework 6:<BR>
<!WA31><A href=http://www.cs.uiowa.edu/~cremer/courses/cs21/homeworks/testdata1.text>testdata11</A>,
<!WA32><A href=http://www.cs.uiowa.edu/~cremer/courses/cs21/homeworks/testdata2.text>testdata2</A>,
<!WA33><A href=http://www.cs.uiowa.edu/~cremer/courses/cs21/homeworks/testdata3.text>testdata3</A> <BR>
<!WA34><A href=http://www.cs.uiowa.edu/~cremer/courses/cs21/homeworks/testdata4.text>testdata4</A>,
<!WA35><A href=http://www.cs.uiowa.edu/~cremer/courses/cs21/homeworks/testdata5.text>testdata5</A>,
<!WA36><A href=http://www.cs.uiowa.edu/~cremer/courses/cs21/homeworks/testdata6.text>testdata6</A>
<LI> <!WA37><A HREF=http://www.cs.uiowa.edu/~cremer/courses/cs21/homeworks/hw5/hw5.html>Homework 5</A> (HTML version).<BR>
     <!WA38><A HREF=http://www.cs.uiowa.edu/~cremer/courses/cs21/homeworks/hw5.ps>Homework 5</A> (Postscript version).
<LI> <!WA39><A HREF=http://www.cs.uiowa.edu/~cremer/courses/cs21/homeworks/hw4/hw4.html>Homework 4</A> (HTML version).<BR>
     <!WA40><A HREF=http://www.cs.uiowa.edu/~cremer/courses/cs21/homeworks/hw4.ps>Homework 4</A> (Postscript version).
<LI> <!WA41><A HREF=http://www.cs.uiowa.edu/~cremer/courses/cs21/homeworks/hw3/hw3.html>Homework 3</A> (HTML version).<BR>
     <!WA42><A HREF=http://www.cs.uiowa.edu/~cremer/courses/cs21/homeworks/hw3.ps>Homework 3</A> (Postscript version).
<LI> <!WA43><A HREF=http://www.cs.uiowa.edu/~cremer/courses/cs21/homeworks/hw2/hw2.html>Homework 2</A> (HTML version).<BR>
     <!WA44><A HREF=http://www.cs.uiowa.edu/~cremer/courses/cs21/homeworks/hw2.ps>Homework 2</A> (Postscript version).
<LI> <!WA45><A HREF=http://www.cs.uiowa.edu/~cremer/courses/cs21/homeworks/hw1.ps>Homework 1</A> (Postscript file).
For those who can't view or print Postscript, here's
an HTML (the basic WWW language) version 
<!WA46><A HREF=http://www.cs.uiowa.edu/~cremer/courses/cs21/homeworks/hw1/hw1.html>Homework 1</A>. <BR>
</UL>


<HR>
<H2>
<A NAME=grades> Scores and grades
</H2>
<P>
<UL>
<LI> Course grades: 
<PRE>
      Total score:
          > 460                    A+
      415 - 459                    A
      400 - 414                    A-
      390 - 399                    B+
      385 - 389                    B
      370 - 379                    B-
      350 - 369                    C+
      320 - 349                    C
      270 - 319                    C-
      250 - 269                    D
          < 250                    F

NOTE: the two highest scorers were graduate students.  The allocation of
letter grades for the rest of the class was done independently of their scores.
</PRE>       
<LI> <!WA47><A HREF=http://www.cs.uiowa.edu/~cremer/courses/cs21/grades-by-id>Complete homework and exam scores, including final</A>. 
Sorted by ID number. (plain text file) <br>
<LI> <!WA48><A HREF=http://www.cs.uiowa.edu/~cremer/courses/cs21/grades-by-score> Complete homework and exam scores, including final</A>.
Sorted by total score. (plain text file) 
<LI> Final Exam data. Median: 87.  Mean: 87.  High 115. 
<PRE>
      Score range           Number of people
          > 110                    2
      101 - 110                    6
       91 - 100                    4
       81 -  90                    9
       71 -  80                   10
         <=  70                    4
</PRE>
<LI> Exam 2 data. Median: 72.  Mean: 71.9.  High 97. 
<PRE>
      Score range           Number of people
          > 95                     2
       81 - 90                     7
       71 - 80                    11 
       61 - 70                     9
         <= 60                     6
</PRE>
<LI> Exam 1 data. Median: 80/81.  Mean: 76.0.  High 98. 
<PRE>
      Score range           Number of people
          > 90                     5
       81 - 90                    13
       71 - 80                     7
       61 - 70                     2
         <= 60                     9
</PRE>
</UL>

<HR>
<H2>
<A NAME=solns> Homework Solutions, useful code, and miscellaneous stuff
</H2>
<P>
<UL>
<LI> <!WA49><A HREF=http://www.cs.uiowa.edu/~cremer/courses/cs21/solutions/hw8-sol/hw8-sol.html>Homework 8 solutions</A> (HTML version).<BR>
     <!WA50><A HREF=http://www.cs.uiowa.edu/~cremer/courses/cs21/solutions/hw8-sol.ps>Homework 8 solutions</A> (Postscript version). 
<LI> C++ code for Question 2 on Homework 8.  Code is not commented and does
not quite meet the specifications for Question 2 (it reads the input interactively
rather than from a file, handles only single character "words", and prints
the tree in preorder rather than level order), but the important part, the 
one that fills in the table used to calculate the optimal binary search tree,
is as it should be.<br>  
There are two ASCII files - <!WA51><A HREF=http://www.cs.uiowa.edu/~cremer/courses/cs21/solutions/obst.H>obst.H</A>
and <!WA52><A HREF=http://www.cs.uiowa.edu/~cremer/courses/cs21/solutions/obst.C>obst.C</A>.
<LI> <!WA53><A HREF=http://www.cs.uiowa.edu/~cremer/courses/cs21/solutions/exam2-sol/exam2-sol.html>Exam 2 solutions</A> (HTML version).<BR>
     <!WA54><A HREF=http://www.cs.uiowa.edu/~cremer/courses/cs21/solutions/exam2-sol.ps>Exam 2 solutions</A> (Postscript version). 
<LI> <!WA55><A HREF=http://www.cs.uiowa.edu/~cremer/courses/cs21/solutions/hw7-sol/hw7-sol.html>Homework 7 solutions</A> (HTML version).<BR>
     <!WA56><A HREF=http://www.cs.uiowa.edu/~cremer/courses/cs21/solutions/hw7-sol.ps>Homework 7 solutions</A> (Postscript version). 
<LI> <!WA57><A HREF=http://www.cs.uiowa.edu/~cremer/courses/cs21/solutions/hw6-sol/hw6-sol.html>Homework 6 solutions</A> (HTML version).<BR>
     <!WA58><A HREF=http://www.cs.uiowa.edu/~cremer/courses/cs21/solutions/hw6-sol.ps>Homework 6 solutions</A> (Postscript version). 
<LI> <!WA59><A HREF=http://www.cs.uiowa.edu/~cremer/courses/cs21/solutions/hw5-sol/hw5-sol.html>Homework 5 solutions</A> (HTML version).<BR>
     <!WA60><A HREF=http://www.cs.uiowa.edu/~cremer/courses/cs21/solutions/hw5-sol.ps>Homework 5 solutions</A> (Postscript version). 
<LI> <!WA61><A HREF=http://www.cs.uiowa.edu/~cremer/courses/cs21/solutions/hw4-sol/hw4-sol.html>Homework 4 solutions</A> (HTML version).<BR>
     <!WA62><A HREF=http://www.cs.uiowa.edu/~cremer/courses/cs21/solutions/hw4-sol.ps>Homework 4 solutions</A> (Postscript version). 
<LI> Sample exam that might help you see the style of questions you'll get
on Exam 1 (Wed., Feb. 28).   The exam was given at about this point in 
the course during the fall semester, 1993.  The document here contains
two extra questions that were not actually used on the exam.<BR> 
<!WA63><A HREF=http://www.cs.uiowa.edu/~cremer/courses/cs21/etc/old-exam/old-exam.html>Sample exam in HTML</A><BR>
<!WA64><A HREF=http://www.cs.uiowa.edu/~cremer/courses/cs21/etc/old-exam.ps>Sample exam in Postscript</A>
<LI> <!WA65><A HREF=http://www.cs.uiowa.edu/~cremer/courses/cs21/solutions/hw3-sol/hw3-sol.html>Homework 3 solutions</A> (HTML version).<BR>
     <!WA66><A HREF=http://www.cs.uiowa.edu/~cremer/courses/cs21/solutions/hw3-sol.ps>Homework 3 solutions</A> (Postscript version).
<LI> <!WA67><A HREF=http://www.cs.uiowa.edu/~cremer/courses/cs21/etc/heap.c++> Implementation of heap routines in C++</A><br>
Maybe useful for last question on Homework 4.  Pascal code is available
via ftp site listed in beginning of textbook.
<LI> <!WA68><A HREF=http://www.cs.uiowa.edu/~cremer/courses/cs21/solutions/hw2-sol/hw2-sol.html>Homework 2 solutions</A> (HTML version).<BR>
     <!WA69><A HREF=http://www.cs.uiowa.edu/~cremer/courses/cs21/solutions/hw2-sol.ps>Homework 2 solutions</A> (Postscript version). <BR>
     For code for the MAJORITY problem of Homework 2, see the item below.
<LI> C implementations of solution to MAJORITY problem of Homework 2.
     Linear-time recursive divide-and-conquer method <!WA70><A HREF=http://www.cs.uiowa.edu/~cremer/courses/cs21/etc/maj-by-d-and-c.c>
     maj-by-d-and-c.c</A>, very short simple linear-time scanning method
     <!WA71><A HREF=http://www.cs.uiowa.edu/~cremer/courses/cs21/etc/maj-by-scan.c> maj-by-scan.c</A>.  Code to help generate
     test data for the MAJORITY problem - <!WA72><A HREF=http://www.cs.uiowa.edu/~cremer/courses/cs21/etc/gen-maj-test-data.c>
     gen-maj-test-data.c</A>.  A number of test data files are contained
     in the directory <!WA73><A HREF=http://www.cs.uiowa.edu/~cremer/courses/cs21/etc/maj-test-data> etc/maj-test-data</A>.
     Files:  <!WA74><A HREF=http://www.cs.uiowa.edu/~cremer/courses/cs21/etc/maj-test-data/maj-data-1> etc/maj-test-data/maj-data-1</A>,
     <!WA75><A HREF=http://www.cs.uiowa.edu/~cremer/courses/cs21/etc/maj-test-data/maj-data-2> etc/maj-test-data/maj-data-2</A>,
     <!WA76><A HREF=http://www.cs.uiowa.edu/~cremer/courses/cs21/etc/maj-test-data/maj-data-3> etc/maj-test-data/maj-data-3</A>,
     <!WA77><A HREF=http://www.cs.uiowa.edu/~cremer/courses/cs21/etc/maj-test-data/maj-data-8> etc/maj-test-data/maj-data-8</A>,
     <!WA78><A HREF=http://www.cs.uiowa.edu/~cremer/courses/cs21/etc/maj-test-data/maj-data-16> etc/maj-test-data/maj-data-16</A>,
     <!WA79><A HREF=http://www.cs.uiowa.edu/~cremer/courses/cs21/etc/maj-test-data/maj-data-100> etc/maj-test-data/maj-data-100</A>,
     <!WA80><A HREF=http://www.cs.uiowa.edu/~cremer/courses/cs21/etc/maj-test-data/maj-data-1000a> etc/maj-test-data/maj-data-1000a</A>,
     <!WA81><A HREF=http://www.cs.uiowa.edu/~cremer/courses/cs21/etc/maj-test-data/maj-data-1000b> etc/maj-test-data/maj-data-1000b</A>,
     <!WA82><A HREF=http://www.cs.uiowa.edu/~cremer/courses/cs21/etc/maj-test-data/maj-data-1000c> etc/maj-test-data/maj-data-1000c</A>,
     <!WA83><A HREF=http://www.cs.uiowa.edu/~cremer/courses/cs21/etc/maj-test-data/maj-data-1000d> etc/maj-test-data/maj-data-1000d</A>.

     Source code is basic C.  Only tested on Silicon Graphics workstation
     runing IRIX (Silicon Graphics' Unix).  The two MAJORITY implementations
     should compile fine on other machines/compilers (e.g. just 
     use cc -o maj-by-scan maj-by-scan.c).  The gen-maj-test-data.c code
     contains a call to drand48, which is, I'd guess is a Unix specific
     random number generator.  It should be easy to change the code to 
     run elsewhere, however.
<LI> <!WA84><A HREF=http://www.cs.uiowa.edu/~cremer/courses/cs21/solutions/hw1-sol/hw1-sol.html>Homework 1 solutions</A> (HTML version).<BR>
     <!WA85><A HREF=http://www.cs.uiowa.edu/~cremer/courses/cs21/solutions/hw1-sol.ps>Homework 1 solutions</A> (Postscript version).
</UL>

</BODY>
